package main

func minFallingPathSum(matrix [][]int) int {
	dp := make([][]int, len(matrix))
	for i := range dp {
		dp[i] = make([]int, len(matrix))
		for j := range dp[i] {
            dp[i][j] = 1<<31
        }
	}
	for i, row := range matrix {
		for j := range row {
			if i == 0 {
				dp[i][j] = matrix[i][j]
			} else {
				min := 1 << 31
				for k, v := range dp[i-1] {
					if j == k {
						continue
					}
					if v < min {
						min = v
					}
				}
				dp[i][j] = min + matrix[i][j]
			}
		}
	}
	min := 1 << 31
	for _, v := range dp[len(dp)-1] {
		if v < min {
			min = v
		}
	}
	return min
}

func main() {
	m := [][]int{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
	}
	res := minFallingPathSum(m)
	println(res)
}
